The predicated execution of instructions by an instruction-based data processor is a processing technique used to conditionally execute a particular instruction based on the value of a Boolean source operand, referred to as a predicate. Variable Length Execution Set (VLES) architectures are instruction-based data processors that execute multiple instructions in parallel with each other, wherein the number of instructions in a VLES can vary. VLES architectures can be pipelined, wherein each VLES is executed in a plurality of sequential stages. One type of VLES architecture supports the predicated execution of instructions. External trace tools that are used to monitor the status of a program's flow need the predicate information in order to accurately resolve predicated instructions. During Debug, predicate tracing can be performed with a history buffer by adding a bit to the buffer for each predicate that could be updated in a VLES. For example, if the predicate was set, the reported bit in the buffer is one (1), and 0 if it was cleared, regardless of the previous value of the predicate. In response to several predicates being updated by a VLES, they can be reported according to a predicate index, from lower to higher.